//
//  Problem17.swift
//  LeetCode - 17 - 电话号码的字母组合
//
//  Created by 武侠 on 2020/7/7.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit
/*
 [17 电话号码的字母组合]
 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

 示例:
 输入："23"
 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 说明:
 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 */
class Problem17: NSObject {
    func solution() {
//        print("result =", letterCombinations("23"))
        print("result =", letterCombinations2("23"))
    }
    
    let dic:[Character: String] = ["2" : "abc",
                                   "3" : "def",
                                   "4" : "ghi",
                                   "5" : "jkl",
                                   "6" : "mno",
                                   "7" : "pqrs",
                                   "8" : "tuv",
                                   "9" : "wxyz"];
    var vLists:[String] = []
    // 方式1: 回溯法: 循环+递归
    func letterCombinations(_ digits: String) -> [String] {
        // 存储最终的结果的数组
        if digits.count == 0 {
            return []
        }
        
        VDS("", 0, digits)
        return self.vLists
    }
    
    func VDS(_ str: String, _ i: Int, _ digits: String) {
        if i == digits.count {
            vLists.append(str)
            return;
        }
        
        // 获取第i个数组所对应的值 例如: 2: abc
        let strIndex = digits.index(digits.startIndex, offsetBy: i)
        let value = dic[digits[strIndex]]!
        
        // 获取abc里面每个字符,然后回调自己 获取一下个数字的字符
        for ch in value {
            VDS(str + String(ch), i+1, digits)
        }
    }
    
    // 方式2:
    func letterCombinations2(_ digits: String) -> [String] {
        // 存储最终的结果的数组
        if digits.count == 0 {
            return []
        }
        
        for (i, num) in digits.enumerated() {
            // 临时存储
            var temp:[String] = []
            let value = dic[num]!
            for ch in value {
                if i == 0 {
                    temp.append(String(ch))
                } else {
                    for vStr in self.vLists {
                        temp.append(vStr + String(ch))
                    }
                }
            }
            
            self.vLists.removeAll()
            self.vLists.append(contentsOf: temp)
        }
        
        return self.vLists
    }
}
